#include <iostream>
#include <vector>
#include <unordered_map>
#include <cstring>
#include <cmath>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
#define endl '\n'
const int N = 2e3 + 10;
const int INF = 0x3f3f3f3f;
int a[N];
int n;
int dp[N]; 
int suf[N], pre[N];
int gcd(int a, int b)
{
    return b == 0 ? a : gcd(b, a % b);
}


void solve() 
{
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i];
    // 预处理 pre suf数组
    for(int i = 1; i <= n; i++)
    {
        for(int j = i - 1; j >= 1; j--)
        {
            if(gcd(a[i], a[j]) != 1) 
            {
                pre[i] = j;
                break;
            }
        }
        suf[i] = n + 1;
        for(int j = i + 1; j <= n; j++)
        {
            if(gcd(a[i], a[j]) != 1) 
            {
                suf[i] = j;
                break;
            }
        }
    }
    // 预处理（1，i）区间的合法性
    for(int i = 2; i <= n; i++)
    {
        dp[i] = 1;
        for(int j = 1; j <= i; j++)
        {
            if(!(pre[j] >= 1 || suf[j] <= i))
            {
                dp[i] = 0;
                break;
            }
        }
    }
    // 判断（i + 1， r）区间的合法性 + 状态转移
    for(int r = 4; r <= n; r++)
    {
        int minp = suf[r] > r ? pre[r] : INF; 
        for(int i = r - 1 - 1; i >= 2; i--)
        {
            if(suf[i + 1] > r) minp = min(minp, pre[i + 1]);
            if(minp >= i + 1 && dp[i] != 0) dp[r] = max(dp[r], dp[i] + 1);
        }
    }
    cout << (dp[n] == 0 ? -1 : dp[n]) << endl;
}

int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int T = 1;  
	// cin >> T;
	while(T--)
	{
        solve();
	}
	return 0;
}



// #include <iostream>
// #include <vector>
// #include <unordered_map>
// #include <cstring>
// #include <cmath>
// using namespace std;
// typedef long long LL;
// typedef pair<int, int> PII;
// #define endl '\n'
// const int N = 2e3 + 10;
// int a[N];
// int n;
// int dp[N][N]; // dp[l][r] 表示l， r区间内最大的划分数

// int gcd(int a, int b)
// {
//     return b == 0 ? a : gcd(b, a % b);
// }

// int calc(int l, int r)
// {
//     if(dp[l + 1][r] == 0 || dp[l][r - 1] == 0) return 0;
//     for(int i = l + 1; i <= r; i++)
//     {
//         if(gcd(a[l], a[i]) != 1) return 1;
//     }
//     for(int i = l; i <= r - 1; i++)
//     {
//         if(gcd(a[r], a[i]) != 1) return 1;
//     }
//     return 0;
// }

// void solve() 
// {
//     cin >> n;
//     for(int i = 1; i <= n; i++) cin >> a[i];
//     for(int i = 1; i < n; i++)
//         if(gcd(a[i], a[i + 1]) != 1)
//             dp[i][i + 1] = 1;
//     for(int len = 3; len <= n; len++)
//     {
//        for(int l = 1; l + len - 1 <= n; l++)
//        {
//             int r = l + len - 1;
//             for(int i = l + 1; i <= r - 2; i++)
//             {
//                 // if(dp[l][i] == 0 || dp[i + 1][r] == 0) continue;
//                 dp[l][r] = max(dp[l][r], dp[l][i] + dp[i + 1][r]);
//             }
//             if(dp[l][r] == 0) dp[l][r] = calc(l, r);
//        }
//     }
//     // for(int i = 1; i <= n; i++)
//     // {
//     //     for(int j = 1; j <= n; j++)
//     //     {
//     //         cout << dp[i][j] << ' ';
//     //     }
//     //     cout << endl;
//     // }
//     cout << (dp[1][n] == 0 ? -1 : dp[1][n]) << endl;
// }

// int main()
// {
//     ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
//     int T = 1;  
// 	// cin >> T;
// 	while(T--)
// 	{
//         solve();
// 	}
// 	return 0;
// }



